package SortMethod;

import SortHelper.SortHelper;

public class QuickSort {

    private QuickSort(){}

    //快排的接口，传入一个数组
    public static <E extends Comparable<E>> void sort(E[] arr){
        sort(arr,0,arr.length-1);
    }

    //快排的内部递归
    private static <E extends Comparable<E>> void sort(E[] arr,int l,int r){
        if (l >= r)return;
        //整体一分为二
        int p = partition(arr,l,r);
        //左边的数来一次
        sort(arr,l,p-1);
        //右边的数来一次
        sort(arr,p+1,r);
    }

    //快排的核心功能，返回数组中的一个数并且令这个数左边都比它小，右边都比它大
    private static <E extends Comparable<E>> int partition(E[]arr,int l,int r){
        int p = l;
        for (int i = l+1; i <= r; i++) {
            if (arr[p].compareTo(arr[i]) > 0){
                SortHelper.swap(arr,p,i);
                p = i;
            } else {
                SortHelper.swap(arr,i,r--);
                i--;
            }
        }
        return p;
    }
}
